package l.l.w.practice.BinaryTree;


import java.util.Random;

/**
 * Created by llw on 2017/9/12.
 *学习二叉搜索树。
 */

public class BinarySearchTreeLearn {
    /**
     * 构造一颗二叉搜索树
     * @param num
     * @return
     */
    public static BinarySearchTreeNode constructTree(int num){
        Random random = new Random();
        int[] allValues = new int[num];
        for(int i=0;i<num;++i){
            allValues[i]=random.nextInt(num);
        }
        BinarySearchTreeNode root = new BinarySearchTreeNode(allValues[0]);
        for(int i = 1;i < num; ++i){
            treeInsert(root,allValues[i]);
        }

        return root;
    }

    /**
     * 给二叉搜索树中插入一个节点
     * @param root
     * @param value
     */
    public static void treeInsert(BinarySearchTreeNode root, int value) {
        if(root.value >= value){
            if(root.left!=null){
                treeInsert((BinarySearchTreeNode) root.left,value);
            }else{
                BinarySearchTreeNode node = new BinarySearchTreeNode(value);
                root.left = node;
                node.parent = root;
            }
        }else{
            if(root.right != null){
                treeInsert((BinarySearchTreeNode) root.right,value);
            }else{
                BinarySearchTreeNode node = new BinarySearchTreeNode(value);
                root.right = node;
                node.parent = root;
            }
        }
    }



    public static void main(String[] args) {
        BinarySearchTreeNode root = BinarySearchTreeLearn.constructTree(10);
        BinaryTreeLearn.printTree(root);
        System.out.println(root);
    }
}


class BinarySearchTreeNode extends BinaryTreeNode {
    BinaryTreeNode parent;

    BinarySearchTreeNode(int value){
        super(value);
    }
}
